class Solution {
public:
    ListNode* reserve(ListNode* begin, ListNode* end) {
        ListNode* pre = nullptr;
        ListNode* cur = begin;
        ListNode* next = nullptr;

        while (cur != end) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre; // 返回反转后的头节点
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (!head || m == n) {
            return head;
        }

        // 创建一个哨兵节点
        ListNode dummy(-1);
        dummy.next = head;
        ListNode* newbegin = &dummy;

        // 找到要翻转的前一个节点
        for (int i = 1; i < m; i++) {
            newbegin = newbegin->next;
        }

        ListNode* begin = newbegin->next; // 要翻转的起点节点
        ListNode* end = begin;

        // 找到要翻转的终点节点
        for (int i = m; i < n; i++) {
            end = end->next;
        }

        ListNode* newend = end->next; // 记录翻转后连接的节点
        end->next = nullptr; // 断开链表

        // 反转begin到end部分的节点
        newbegin->next = reserve(begin, end->next); // 反转并连接
        begin->next = newend; // 连接反转后的部分和后面的部分
        
        return dummy.next; // 返回新的头节点
    }
};